// https://www.lintcode.com/problem/search-in-rotated-sorted-array/my-submissions

class Solution {
public:
    /**
     * @param A: an integer rotated sorted array
     * @param target: an integer to be searched
     * @return: an integer
     */
    int search(vector<int> &A, int target) {
        if (A.empty()) return -1;
        int low = 0;
        int high = A.size() - 1;
        while (low + 1 < high)
        {
            int mid = (high - low) / 2 + low;
            if (A[mid] == target) return mid;
            if (A[mid] > A[low])
            {
                if (A[mid] > target && A[low] <= target) high = mid;
                else low = mid;
            }
            else
            {
                if (A[mid] < target && A[high] >= target) low = mid;
                else high = mid;
            }
        }
        if (A[low] == target) return low;
        if (A[high] == target) return high;
        return -1;
    }
};